//SA
//$Id: sa_common.h 441 2010-04-09 17:27:20Z Oleg.Bulychov $
#pragma once

//__________________________________________________________________________________
#include "src/heo/include/random.h"
#include "src/heo/include/stream_visitor.h"
#include "src/heo/include/xml_file.h"
#include "src/heo/include/optimization_direction.h"
#include "src/heo/include/solution.h"
#include "src/heo/include/stop_condition.h"
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
enum
{
    sa_update_if_better,
    sa_always_update
};
//__________________________________________________________________________________
//__________________________________________________________________________________
template<class E>
struct SA_Traits
{
    typedef E TEnvironment;
};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
struct sa_tag
{};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
template<class T>
class SA
{
    DISALLOW_COPY_AND_ASSIGN(SA);
public:
    typedef typename T::TEnvironment TEnvironment;
    typedef solution<typename TEnvironment::TSolution, sa_tag> TSolution;

    typedef typename TSolution::TDirection TDirection;
    typedef typename TSolution::TCostType  TCostType;
protected:
    TEnvironment*           env_;
    int                     rank_;
    uniform_random          rnd_;

    std::vector< ref_ptr< stop_condition::abstract_stop_condition<TEnvironment,
        TSolution> > > stop_condition_;
    int                     max_step_;
    int                     pending_stop_;
    int                     sent_stop_;

    TSolution               current_;
    TSolution               best_;
    TSolution               tmp_;
    double                  t_;

    TCostType               prev_cost_;
    bool                    prev_cost_init_;

    double                  move_probability_;
    double                  initial_temperature_;
    double                  cooling_rate_;
    double                  heating_rate_;
    int                     isotherm_moves_;
    int                     update_policy_;
    bool                    debug_flag_;
public:
    explicit SA(): env_(NULL),
        rank_(0),
        rnd_(0),
        max_step_(0),
        pending_stop_(0),
        sent_stop_(0),
        prev_cost_(),
        prev_cost_init_(),
        t_(),
        debug_flag_()
    {
        stop_condition::max_step<TEnvironment, TSolution>::instantiate();
        stop_condition::cost_limit<TEnvironment, TSolution>::instantiate();
        hidden::instantiate_ptr_visit((stop_condition::max_step<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
        hidden::instantiate_ptr_visit((stop_condition::cost_limit<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
    }

    static char const* get_Name() { return "sa"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(move_probability),           0.02);
        v(VAR_(initial_temperature),        1.);
        v(VAR_(cooling_rate),               0.994);
        v(VAR_(heating_rate),               1.5);
        v(VAR_(isotherm_moves),             20);
        v(VAR_(update_policy),              0);

        v(VAR_(stop_condition),             stop_condition::validator<
            stop_condition::max_step<TEnvironment, TSolution> >());
    }

    TEnvironment* get_Environment() const { return env_; }

    int get_Rank() const { return rank_; }

    uniform_random& get_Rnd() { return rnd_; }

    void init(TEnvironment* env, int rank, int thread_id, bool debug_flag = false)
    {
        if (!env_)
        {
            env_ = env;
            rank_ = rank;
            rnd_.set_Thread_Id(thread_id);
            tmp_.init(env_, rnd_);
            current_.init(env_, rnd_);
            if (update_policy_ == sa_update_if_better)
                best_.init(env_, rnd_);
            debug_flag_ = debug_flag;
        }
        else
        {
            ASSERT_(env_ == env);
            ASSERT_(rank_ == rank);
        }
    }

    int get_Default_Solution_Pool_Size() const
    {
        return 1;
    }

    template<class TInSolution>
    void set_Initial_Solution(TInSolution const& sol)
    {
        current_.assign(sol);
        current_.evaluate(env_, rnd_);
        if (update_policy_ == sa_update_if_better)
            best_.assign(current_);
    }

    template<class TInOutSolution>
    void init_From_Pool(Solution_Pool<TInOutSolution>& pool)
    {
        ASSERT_(pool.sol_list_.size() <= 1);
        if (pool.sol_list_.empty())
        {
            current_.init(env_, rnd_);
            current_.generate(env_, rnd_);
        }
        else
        {
            current_.assign(pool.sol_list_.front());
        }
        current_.evaluate(env_, rnd_);
        if (update_policy_ == sa_update_if_better)
            best_.assign(current_);
    }

    void set_Initial_Temperature()
    {
        t_ = initial_temperature_;
        //std::cout << "***init t:" << t_ << ", cost = " << current_.get_Cost() << std::endl;
        if (heating_rate_ > 1.)
        {
            for(;;)
            {
                int sum = 0;
                for (int i = 0; i < 10; ++i)
                {
                    move();
                    if (is_Acceptable_Solution())
                    {
                        //std::cout << "*ACCEPTABLE " << tmp.get_Cost() << std::endl;
                        ++sum;
                    }
                }
                //std::cout << "***sum = " << sum << std::endl;
                if (sum >= 8)//:TODO review: 80%
                    break;
                t_ *= heating_rate_;
            }
        }
        debug_Print_Temperature();
    }

    void move()
    {
        tmp_.assign(current_);
        tmp_.move(env_, rnd_, move_probability_);
        //if (tmp.changed_)
        //    std::cout << "***move " << std::endl;
        tmp_.evaluate(env_, rnd_);
    }

    void accept_Solution()
    {
        current_.assign(tmp_);
    }

    bool is_Acceptable_Solution()
    {
        return is_Acceptable(meta::int2type<TDirection::direction>());
    }

    bool is_Acceptable(meta::int2type<OPT_MAXIMIZE>)
    {
        TCostType new_cost = tmp_.get_Cost();
        TCostType cur_cost = current_.get_Cost();
        if (new_cost > cur_cost)
            return true;
        return rnd_.next_Double() * (1. + exp((cur_cost - new_cost) / t_ )) < 2.;
    }

    bool is_Acceptable(meta::int2type<OPT_MINIMIZE>)
    {
        TCostType new_cost = tmp_.get_Cost();
        TCostType cur_cost = current_.get_Cost();
        if (new_cost < cur_cost)
            return true;
        return rnd_.next_Double() * (1. + exp((new_cost - cur_cost) / t_ )) < 2.;
    }

    void update_Temperature(int step)
    {
        if ((step % isotherm_moves_) == 0)
        {
            t_ *= cooling_rate_;
            debug_Print_Temperature();
        }
    }

    void debug_Print_Temperature()
    {
        if (rank_ >= get_Debug_Level())
            return;
        std::cout << std::setw(2) << rank_ << ": new t=" << t_ << std::endl;
    }

    void update_Best_Solution()
    {
        ASSERT_(update_policy_ == sa_update_if_better);
        TCostType cost = current_.get_Cost();
        if (TDirection()(cost, best_.get_Cost()))
            current_.copy_To(best_);
    }

    int get_Debug_Level() const
    {
        int level = env_->debug_level_;
        if (debug_flag_)
            level = (env_->debug_level_ >> 16);
        return level;
    }

    void show_Progress(int step)
    {
        if (rank_ >= get_Debug_Level())
            return;
        TCostType cost = current_.get_Cost();

#pragma omp critical(debug_output)
        if (prev_cost_init_)
        {
            if (TDirection()(prev_cost_, cost))
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "<<<WORSE: " << cost <<
                    " -" << Abs(cost - prev_cost_) << std::endl;
            }
            else if (TDirection()(cost, prev_cost_))
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << ">>>BETTER: " << cost <<
                    " +" << Abs(cost - prev_cost_) << std::endl;
                prev_cost_ = cost;
            }
            else
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "===SAME: " << cost << std::endl;
            }
        }
        else
        {
            std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "###INITIAL: " << cost << std::endl;
            prev_cost_ = cost;
            prev_cost_init_ = true;
        }
    }

    template<class V>
    void emigrate(V& v)
    {
        v << current_;
    }

    template<class V>
    void immigrate(V& v)
    {
        v >> tmp_;
    }

    TSolution& get_Final_Solution()
    {
        if (update_policy_ == sa_update_if_better)
            return best_;
        return current_;
    }

    template<class Send>
    void send_Stop(Send& out)
    {
        out << pending_stop_;
        if (pending_stop_)
        {
            sent_stop_ = 1;
            if (rank_ < env_->debug_level_)
            {
#pragma omp critical(debug_output)
                std::cout << rank_ << ": stop sent" << lf;
            }
        }
    }

    template<class Recv>
    void recv_Stop(Recv& in)
    {
        int stop = 0;
        in >> stop;
        if (stop)
        {
            pending_stop_ = 1;
            if (rank_ < env_->debug_level_)
            {
#pragma omp critical(debug_output)
                std::cout << rank_ << ": stop received" << lf;
            }
        }
    }

    bool stop(int nStep)
    {
        TCostType best_cost = get_Final_Solution().get_Cost();
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            if (stop_condition_[i]->stop(*env_, best_cost, nStep))
                return true;
        }
        return false;
    }

    void calc_Max_Step()
    {
        max_step_ = INT_MAX;
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            int t = stop_condition_[i]->get_Max_Step();
            if (t < max_step_)
                max_step_ = t;
        }
    }

    template<class TInOutSolution>
    void solve(TInOutSolution& sol)
    {
        set_Initial_Solution(sol);
        set_Initial_Temperature();
        calc_Max_Step();
        show_Progress(0);
        for (int step = 1; step <= max_step_; ++step)
        {
            move();
            if (is_Acceptable_Solution())
            {
                accept_Solution();
                show_Progress(step);
                if (update_policy_ == sa_update_if_better)
                    update_Best_Solution();
            }
            if (stop(step))
                break;
            update_Temperature(step);
        }
        sol.assign(get_Final_Solution());
    }
};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________

//EOF!
